package leetcode.year2021.month10;

import java.util.*;
import java.util.stream.Collectors;

//  39. 组合总和

public class _14_02CombinationSum39 {
  /**
   *
   * @param candidates
   * @param target
   * @return
   *
   * 初步思路： 1. 逐个遍历寻值，可以考虑用回溯
   *
   * 解决思路：1. 由于元素可复用，回溯时，需要重复增加一次自己的值
   */
  public List<List<Integer>> combinationSum(int[] candidates, int target) {

    ArrayList<List<Integer>> ans = new ArrayList<>();
    ArrayList<Integer> combine = new ArrayList<>();

    int n = candidates.length;
    if (n == 0){
      return ans;
    }

    getAvailResult(ans,0,candidates,target,combine);

    return ans;

  }

  private void getAvailResult(ArrayList<List<Integer>> ans, int index, int[] candidates, int target, ArrayList<Integer> list) {
    if (index == candidates.length){
      return;
    }
    if (target == 0){
      ans.add(new ArrayList<Integer>(list));
    }
    // 直接跳过
    getAvailResult(ans,index+1,candidates,target,list);
    // 选择当前数
    if (target - candidates[index] >= 0) {
      list.add(candidates[index]);
      getAvailResult(ans,index,candidates,target,list);
      list.remove(list.size() - 1);
    }
  }
  /**
   * 给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
   *
   * candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。 
   *
   * 对于给定的输入，保证和为 target 的唯一组合数少于 150 个。
   *
   *  
   *
   * 示例 1：
   *
   * 输入: candidates = [2,3,6,7], target = 7
   * 输出: [[7],[2,2,3]]
   * 示例 2：
   *
   * 输入: candidates = [2,3,5], target = 8
   * 输出: [[2,2,2,2],[2,3,3],[3,5]]
   * 示例 3：
   *
   * 输入: candidates = [2], target = 1
   * 输出: []
   * 示例 4：
   *
   * 输入: candidates = [1], target = 1
   * 输出: [[1]]
   * 示例 5：
   *
   * 输入: candidates = [1], target = 2
   * 输出: [[1,1]]
   *  
   *
   * 提示：
   *
   * 1 <= candidates.length <= 30
   * 1 <= candidates[i] <= 200
   * candidate 中的每个元素都是独一无二的。
   * 1 <= target <= 500
   *
   *
   */
}
